
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Grafo
{
	private List<No> vertices;

	public static Grafo criarGrafo()
	{
		Grafo grf = new Grafo();
		grf.vertices = new ArrayList<No>();
        for(int i=0;i<5;i++)
        {
            char c = (char)(97+i);
            grf.vertices.add(new No(""+c));
        }
        grf.vertices.get(2).addConexao(grf.vertices.get(0), 2);//2-0                
        grf.vertices.get(0).addConexao(grf.vertices.get(1), 4);//0-1                
        grf.vertices.get(1).addConexao(grf.vertices.get(2), 5);//1-2                
        grf.vertices.get(1).addConexao(grf.vertices.get(3), 7);//1-3                               
        grf.vertices.get(3).addConexao(grf.vertices.get(2), 8);//3-2                
        grf.vertices.get(3).addConexao(grf.vertices.get(4), 1);//3-4
		return grf;
	}
    public No getNo(String desc)
    {
        No retorno = null;
        for(No u : this.vertices)
        {
            if(u.getDescricao().equals(desc))
            {
                retorno = u;
            }
        }
        return retorno;
    }
	public int intMenorCaminho(No u, No w)
	{
            Queue<No> fila = new LinkedList<No>();
            if(!fila.offer(u)) throw new NullPointerException();
            u.setDistancia(0);
            while(!fila.isEmpty())
            {
                No v = fila.poll();
                No k;
                for( Aresta x : v.getArestas())
                {
                    k = x.getDestino();
                    if( k.getDistancia()==(-1) || k.getDistancia()>x.getPeso()+v.getDistancia() )
                    {
                        k.setDistancia(x.getPeso()+v.getDistancia());
                        if(!fila.offer(k)) throw new NullPointerException();
                    }                    
                }
            }
            return w.getDistancia();
	}
	public String strMenorCaminho(No u, No w)
	{
            Queue<No> fila = new LinkedList<No>();
            if(!fila.offer(u)) throw new NullPointerException();
            u.setDistancia(0);
            u.setCaminho(u.getDescricao());
            while(!fila.isEmpty())
            {
                No v = fila.poll();
                No k;
                for( Aresta x : v.getArestas())
                {
                    k = x.getDestino();
                    if( k.getDistancia()==(-1) || k.getDistancia()>x.getPeso()+v.getDistancia() )
                    {
                        k.setDistancia(x.getPeso()+v.getDistancia());
                        k.setCaminho(v.getCaminho()+"->"+k.getDescricao());
                        if(!fila.offer(k)) throw new NullPointerException();
                    }                    
                }
            }
            return w.getCaminho();
	}
}
